package _mst;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.04. 幂集
 */
public class T0804 {
    private List<List<Integer>> ans;
    private List<Integer> path;
    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        ans = new ArrayList<>();
        path = new ArrayList<>();
        this.nums = nums;
        dfs(nums.length - 1);
        return ans;
    }

    /**
     * 方法一：输入的视角（选或不选）
     */
    private void dfs(int i) {
        if (i < 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 选
        path.add(nums[i]);
        dfs(i - 1);
        path.remove(path.size() - 1);
        // 不选
        dfs(i - 1);
    }

    /**
     * 方法二：答案的视角（枚举选哪个）
     */
    private void dfs2(int i) {
        ans.add(new ArrayList<>(path)); // 固定答案
        for (int j = i; j >= 0; j--) {
            path.add(nums[j]);
            dfs2(j - 1);
            path.remove(path.size() - 1); // 恢复现场
        }
    }
}
